package main

import (
	"fmt"
)

/**
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

https://leetcode.com/problems/two-sum/description/

给定一个数组和一个值，让求出这个数组中两个元素值的和等于这个给定值时这两个元素的下标。输出是有要求的
1， 坐标较小的放在前面，较大的放在后面。
2， 这俩下标不能为零。
*/

/**
解法: 通过hashmap来降低查找的时间复杂度
改进后时间复杂度为O(n)
缺点是任意两个数做了2次判断

*/
//func twoSum(nums []int, target int) []int {
//
//	m := make(map[int]int)
//	for i, v := range nums {
//		m[v] = i
//	}
//	for i, v := range nums {
//		if j, ok := m[target-v]; ok&&(i!=j) {
//			return []int{i, j}
//		}
//	}
//	return nil
//}

/**
解法3:
转换思维，遍历数组，在每个位置判断达成目标值所需的另一份值是否存在于已遍历区域中，判断是否已存在借用哈希表实现
优点: 循环数比上一中解法少 省去了循环向哈希表插入数据，并且每两个数只做一次判断
缺点: 代码可读性差

[]int{3, 2, 4}   6
哈希表中存储的是之前遍历的值
遍历数组，每次判断其实是拿当前值与之前遍历过的值做判断，如果符合预期则返回，不符合预期则下一个循环
索引 值  哈希表数据
0   3   []
1   2   [3:0]
2   4   [3:0,2:1]
*/

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)

	for i := 0; i < len(nums); i++ {
		another := target - nums[i]
		if _, ok := m[another]; ok {
			return []int{m[another], i}
		}
		m[nums[i]] = i
	}
	return nil
}

func main() {
	fmt.Print(twoSum([]int{3, 2, 4}, 6))
}
